   IOI. 19 (Oferte) Intr-un magazin, fiecare tip de produse are un pret. De
exemplu, pretul unei flori este de 2 ICU (Informatics Currency Units) iar
pretul unui vas este de 5 ICU. Pentru a atrage ct mai multi cumparatori,
magazinul introduce anumite oferte speciale.
   O oferta speciala consta din unul sau mai multe produse oferite la un
pret mai mic. Exemple: trei flori se dau pentru 5 ICU n loc de 6, sau doua
vase mpreuna cu o floare costa 10 ICU n loc de 12.
   Sa se scrie un program care calculeaza pretul pe care l da un cumparator
pentru o anumita solicitare. Costul trebuie sa fie ct mai mic posibil, n
functie de ofertele speciale. Nu se poate adauga nimic, chiar daca aceasta
ar duce la scaderea pretului.
   Pentru preturile si ofertele din exemplul de mai sus, cel mai mic pret
platit pentru 3 flori si 2 vase este de 14 ICU: doua vase si o floare costa
(redus) 10 ICU, iar 2 flori costa pretul (normal) de 4 ICU.
Intrare:
   Datele de intrare apar n doua fisiere: INPUT.TXT si OFFER.TXT. Primul
fisier descrie produsele (din "cosul de cumparaturi"). Al doilea fisier
descrie ofertele speciale. Ambele fisiere contin numai numere ntregi.
Prima linie din INPUT.TXT da numarul b de produse diferite din cosul de
cumparaturi (0b5).
Fiecare din cele b linii care urmeaza contine trei valori: c,k,p. Valoarea
c este codul (unic) al unui produs (1c999). Valoarea k indica cte bucati
din acest produs sunt n cos (1k5). Valoarea p este pretul normal pentru
fiecare bucata (1p999). De retinut ca n cos nu pot ncape mai mult de
5*5=25 bucati.
 Prima linie din OFFER.TXT contine numarul s de oferte speciale (0s99).
Fiecare din urmatoarele s linii contine o oferta speciala data prin structura
sa si prin pretul redus oferit. Primul numar n de pe fiecare linie este
numarul de produse diferite care fac parte din oferta (1n5).
Urmatoarele n perechi de numere (c,k) indica situatia n care k bucati
(1k5) din produsul de cod c(1c999) sunt n aceasta oferta. Ultimul
numar p de pe linie arata pretul redus (1p999); acest pret per oferta este
mai mic dect suma preturilor normale.
Iesire:
   Se scrie n fisierul OUTPUT.TXT o linie pe care se afla cel mai mic pret
posibil care trebuie platit pentru produsele din fisierul de intrare.
Exemplu: Daca:
INPUT.TXT
2
7 3 2
8 2 5
OFFER.TXT
2
1 7 3 5
2 7 1 8 2 10
atunci iesirea va fi
OUTPUT.TXT
14
========================================
Solutia 1 (Mihai Stroe)

    Metoda de rezolvare este programare dinamica.
    La pasul k se calculeaza pentru fiecare posibila sub-cerinta (multime de
  produse incluse in cerinta) pretul optim care se obtine cu ofertele
  speciale k,k+1,...nr.oferte+nr. produse. Calculul se realizeaza astfel:
    - fie sub-oferta s1,s2,s3,s4,s5 a cerintei c1,c2,c3,c4,c5 (fiecare
  numar reprezinta numarul de produse de un anumit timp, c[i]>=s[i])
  si oferta k=(k1,k2,k3,k4,k5), k[i]<=s[i]. Se cunoaste optimul realizat
  cu ofertele k,k+1,...nr.oferte+nr. produse pentru sub-cerinta k[i]-s[i];
  daca optimul cerintei s este mai mare decit optimul cerintei k-s+pretul
  ofertei k, se actualizeaza optimul cerintei s. In final se va afisa solutia.

var a:array[0..5,0..5,0..5,0..5,0..5]of word;
    i1,i2,i3,i4,i5,nr,i,j,k,l,m,n,p:word;
    f1,f2,fo:text;
    cod,np,pret:array[1..5]of byte;
    offer:array[1..99,1..5]of byte;
    red:array[1..99]of byte;

procedure readdata;
begin
  assign(f1,'Input.txt');
  assign(f2,'offer.txt');
  assign(fo,'output.txt');
  reset(f1);
  reset(f2);
  readln(f1,n);
  for i:=1 to n do
      readln(f1,cod[i],np[i],pret[i]);
  readln(f2,nr);
  for i:=1 to nr do
      begin
        read(f2,j);
        for k:=1 to j do
            begin
              read(f2,l,p);
              for m:=1 to n do
                  if cod[m]=l then
                     offer[i,m]:=p;
            end;
        readln(f2,red[i]);
      end;
  close(f1);
  close(f2);
end;

procedure solve;
begin
  fillchar(a,sizeof(a),100);
  a[0,0,0,0,0]:=0;
  inc(nr,n);
  for i:=1 to n do
      begin
        offer[nr-n+i,i]:=1;
        red[nr-n+i]:=pret[i];
      end;
  for k:=nr downto 1 do
  for i1:=offer[k,1] to np[1] do
  for i2:=offer[k,2] to np[2] do
  for i3:=offer[k,3] to np[3] do
  for i4:=offer[k,4] to np[4] do
  for i5:=offer[k,5] to np[5] do
      if a[i1,i2,i3,i4,i5]>red[k]+a[i1-offer[k,1],i2-offer[k,2],i3-offer[k,3],i4-offer[k,4],i5-offer[k,5]]
         then a[i1,i2,i3,i4,i5]:=red[k]+a[i1-offer[k,1],i2-offer[k,2],i3-offer[k,3],i4-offer[k,4],i5-offer[k,5]];
  rewrite(fo);
  writeln(fo,a[np[1],np[2],np[3],np[4],np[5]]);
  close(fo);
end;

begin
  readdata;
  solve;
end.
-----------------------------------------
Solutia 2 (Catalin Francu)
program Oferte;
{$B-,I-,R-,S-}
const MaxOffers=99;
      NoItem=100;
type ByteVector=array[1..5] of Byte;
     OfferType=record
                 Qty:ByteVector;
                 ReducedPrice:Integer;
               end;
     OfferVector=array[1..MaxOffers] of OfferType;
     ProductType=record
                   Index,Price:Integer;
                   Qty:Byte;
                 end;
     ProductVector=array[1..5] of ProductType;
     WeirdMatrix=array[0..5,0..5,0..5,0..5,0..5] of Integer;
{ A[i,j,k,l,m]=costul pt. a cumpara i obiecte de tipul 1, j de tipul 2 etc. }
var O:OfferVector;
    P:ProductVector;
    A:WeirdMatrix;
    NO:Integer;

procedure ReadData;
var N,i,j,Ind:Integer;
begin
  Assign(Input,'input.txt');Reset(Input);
  ReadLn(N);
  for i:=1 to N do
    with P[i] do ReadLn(Index,Qty,Price);
  for i:=N+1 to 5 do
    with P[i] do
      begin
        Index:=NoItem;
        Qty:=0;
      end;
  Close(Input);
  Assign(Input,'offer.txt');Reset(Input);
  ReadLn(NO);
  for i:=1 to NO do
    with O[i] do
      begin
        Read(N);
        for i:=1 to 5 do Qty[i]:=0;
        for i:=1 to N do
          begin
            Read(Ind);
            j:=0;
            repeat Inc(j) until P[j].Index=Ind;
            Read(Qty[j]);
          end;
        ReadLn(ReducedPrice);
      end;
  Close(Input);
end;

procedure TryOffers(i,j,k,l,m:Integer);
var u,v,i1,j1,k1,l1,m1:Integer;
begin
  for u:=1 to NO do
    with O[u] do
      begin
        i1:=i-Qty[1];
        j1:=j-Qty[2];
        k1:=k-Qty[3];
        l1:=l-Qty[4];
        m1:=m-Qty[5];
        if (i1>=0) and (j1>=0) and (k1>=0) and (l1>=0) and (m1>=0)
          then if A[i1,j1,k1,l1,m1]+ReducedPrice<A[i,j,k,l,m]
                 then A[i,j,k,l,m]:=A[i1,j1,k1,l1,m1]+ReducedPrice;
      end;
end;

procedure FindCost;
var i,j,k,l,m:Integer;
begin
  for i:=0 to P[1].Qty do
  for j:=0 to P[2].Qty do
  for k:=0 to P[3].Qty do
  for l:=0 to P[4].Qty do
  for m:=0 to P[5].Qty do
    begin
      A[i,j,k,l,m]:=i*P[1].Price+j*P[2].Price+k*P[3].Price+
                    l*P[4].Price+m*P[5].Price;
      TryOffers(i,j,k,l,m);
    end;
end;

procedure WriteSolution;
begin
  Assign(Output,'output.txt');Rewrite(Output);
  WriteLn(A[P[1].Qty,P[2].Qty,P[3].Qty,P[4].Qty,P[5].Qty]);
  Close(Output);
end;

begin
  ReadData;
  FindCost;
  WriteSolution;
end.
------------------------------------
